import numpy as np
from two_d_utils import cross_product, vector, inside_triangle


def convex_hull_bruteforce(points):
    # 对任意的三角形abc，如果任意的点d在三角形内部，则排除点d
    for a in range(len(points)):
        if points[a] is None:
            continue
        for b in range(a + 1, len(points) - 2):
            if points[b] is None:
                continue
            for c in range(b + 1, len(points) - 1):
                if points[c] is None:
                    continue
                for d in range(0, len(points)):
                    if points[d] is None or d in [a, b, c]:
                        continue
                    if inside_triangle((points[a], points[b], points[c]), points[d]):
                        points[d] = None
    # remove removed points
    points = list(filter(lambda p: p is not None, points))

    # sort points by x axis
    points.sort(key=lambda p: p[0])

    left_most, right_most = points[0], points[-1]

    upper_part, lower_part = [], []
    for each in points:
        if cross_product(vector(left_most, right_most), vector(left_most, each)) < 0:
            upper_part.append(each)
        else:
            lower_part.append(each)
    return [left_most] + upper_part + [right_most] + list(reversed(lower_part))
